package 每日一题;

import 二叉树.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @description: 小白白刷题
 * @author: 小白白
 * @create: 2021-05-17
 **/

public class No993二叉树的堂兄弟节点 {

    /**
     * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
     * 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
     * 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
     * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
     *
     * 示例 1：
     * 输入：root = [1,2,3,4], x = 4, y = 3
     * 输出：false
     * 示例 2：
     * 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
     * 输出：true
     * 示例 3：
     * 输入：root = [1,2,3,null,4], x = 2, y = 3
     * 输出：false
     *  
     * 提示：
     * 二叉树的节点数介于 2 到 100 之间。
     * 每个节点的值都是唯一的、范围为 1 到 100 的整数。
     */

    public boolean isCousins(TreeNode root, int x, int y) {

        Deque<TreeNode> queue=new ArrayDeque<>();
        queue.addLast(root);
        int result=0;
        TreeNode cur=null;

        while (!queue.isEmpty()){

            int count=queue.size();

            while (count>0){
                TreeNode treeNode = queue.removeFirst();
                if(treeNode.val==x||treeNode.val==y){
                    /**
                     * 要父节点不同才行,如何找到上层父节点?
                     */
                    result++;
                }
                if(treeNode.left!=null) {
                    queue.addLast(treeNode.left);
                    if(treeNode.left.val==x||treeNode.left.val==y){
                        cur=treeNode;
                    }
                }
                if(treeNode.right!=null) {
                    queue.addLast(treeNode.right);
                    if(treeNode.right.val==x||treeNode.right.val==y){
                        cur=treeNode;
                    }
                }
                count--;
            }

            if(result==2){
                if(cur.left==null||cur.right==null){
                    return true;
                }
                if(cur.left.val==x&&cur.right.val==y){
                    return false;
                }
                if(cur.right.val==x&&cur.left.val==y){
                    return false;
                }
                return true;
            }

            if(result!=0){
                return false;
            }

        }

        return false;
    }

}
